// 力扣25. K 个一组翻转链表
// https://leetcode.cn/problems/reverse-nodes-in-k-group/
package main

import "fmt"

type ListNode struct {
	Next  *ListNode
	value interface{}
}

// 打印链表
func (this *ListNode) Print() {
	cur := this
	format := ""
	for nil != cur {
		format += fmt.Sprintf("%+v", cur.value)
		cur = cur.Next
		if nil != cur {
			format += "->"
		}
	}
	fmt.Println(format)
}

// 思路1：使用递归，时间复杂度: O(N)，空间复杂度: O(N/K)。
func reverseKGroup1(head *ListNode, k int) *ListNode {
	count := 0
	cur := head
	var tmp *ListNode
	for cur != nil && count < k {
		count++
		cur = cur.Next
	}
	// 当前 k-group 压根没有k个node，那么直接保持这个k-group不动返回head
	if count < k {
		return head
	}
	// last是k+1个节点后的链表的翻转结果
	last := reverseKGroup1(cur, k)
	// 从第一个节点开始反转，第一个节点挂在last前面，把last换成第一个节点
	// 第二个节点挂在last前面，继续把last换成第一个节点，直到把k个节点都反转完
	for count = 0; count < k; count++ {
		tmp = head
		head = head.Next
		tmp.Next = last
		last = tmp
	}
	return last
}

// 思路2：使用循环，时间复杂度: O(N)，空间复杂度: O(1)。
func reverseKGroup2(head *ListNode, k int) *ListNode {
	dummy := &ListNode{Next: nil, value: -1}
	dummy.Next = head
	dummy2 := dummy
	for {
		p := dummy2.Next
		start := p
		count := 0
		for count < k && p != nil {
			p = p.Next
			count++
		}
		//如果少于k个节点，则不需要翻转
		if count < k {
			break
		}
		//k个节点后的那个节点
		last := p
		//一个一个连过去
		p = dummy2.Next
		for i := 0; i < k; i++ {
			next := p.Next
			p.Next = last
			last = p
			p = next
		}
		//翻转后的结果
		dummy2.Next = last
		//当前的第k个数据就是先前的第一个数据
		dummy2 = start
	}
	return dummy.Next
}

func main() {
	n5 := &ListNode{value: 5}
	n4 := &ListNode{value: 4, Next: n5}
	n3 := &ListNode{value: 3, Next: n4}
	n2 := &ListNode{value: 2, Next: n3}
	n1 := &ListNode{value: 1, Next: n2}

	n1.Print() //原链表: 1->2->3->4->5

	//递归
	//reverseKGroup1(n1, 2).Print() //每2个节点一组翻转: 2->1->4->3->5
	//reverseKGroup1(n1, 3).Print() //每3个节点一组翻转: 3->2->1->4->5

	//循环
	//reverseKGroup2(n1, 2).Print() //每2个节点一组翻转: 2->1->4->3->5
	reverseKGroup2(n1, 3).Print() //每3个节点一组翻转: 3->2->1->4->5
}
